package com.fengye.algorithms.leecode.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author loupf50246
 * @date 2023/7/23 19:18
 */
public class MaxEnvelopes {

    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes == null || envelopes.length == 0) {
            return 0;
        }

        Arrays.sort(envelopes, (int[] arr1, int[] arr2) -> {
            if (arr1[0] == arr2[0]) {
                return arr2[1] - arr1[1];
            }
            return arr1[0] - arr2[0];
        });

        return lengthOfLIS(envelopes);
    }

    public int lengthOfLIS(int[][] nums) {
        int[] dp = new int[nums.length];
        // 初始化都为1
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i][1] > nums[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

        return max;
    }

    public int lengthOfLISV2(int[][] nums) {
        // list保存的是构成上升子序列
        List<Integer> list = new ArrayList<>();
        for (int[] num : nums) {
            // 如果list为空，直接把num加进去，如果list的最后一个元素小于num,
            // 说明num加入到list的末尾可以构成一个更长的上升子序列，我们就把num加入
            if (list.size() == 0 || list.get(list.size() - 1) < num[1]) {
                list.add(num[1]);
            } else {
                // 如果num不大于list的最后一个元素，用num把list中第一个大于他的值替换掉
                // 这样保证在list中的元素不变的情况下，元素尽可能的小，放尽可能多的数据
                int i = Collections.binarySearch(list, num[1]);
                // 因为list是从小到大排序的，并且上面使用的是二分法查找，
                // 当i小于0的时候，说明出现了重复的，我们直接把他替换掉，
                // 如果i小于0，我们对i取反，他就是list中第一个大于num值的位置，把它替换
                list.set((i < 0) ? -i-1 : i, num[i]);
            }
        }
        return list.size();
    }
}
